package leetCode.solution;

public class Solution10 {
	public boolean isMatch(String s, String p) {
		if (s == null && p == null) {
			return true;
		}
		if (s == null || p == null) {
			return false;
		}
		char sArr[] = s.toCharArray();
		char pArr[] = p.toCharArray();
		
		// 0:未计算,1:true,-1:flase
		int [][] dp = new int[sArr.length+1][pArr.length+1];
		
		return isValid(sArr, pArr) && process(sArr, 0, pArr, 0, dp);
	}

	// s[si....] 能否变成 p[pi...]
	// 重要限制：p[pi]不能压中'*'
	private boolean process(char s[], int si, char p[], int pi, int [][] dp) {
		if(dp[si][pi]!=0) {
			return dp[si][pi]==1;
		}
		boolean result = false;
		if (pi == p.length) {
			result = si == s.length;
			dp[si][pi] = result?1:-1;
			return result;
		}
		
		// pi+1位置不是*
		if(pi+1==p.length || p[pi+1]!='*') {
			return si!=s.length && (s[si]==p[pi] || p[pi]=='.') && process(s, si+1, p, pi+1, dp);
		}
		// pi+1位置是*
		while(si!=s.length && (s[si]==p[pi] || p[pi]=='.')) {
			if(process(s, si++, p, pi+2, dp)) {
				dp[si][pi] = 1;
				return true;
			}
		}
		return process(s, si, p, pi+2, dp);
	}
	
	public static void main(String[] args) {
		System.out.println(new Solution10().isMatchDP("aaa", "a*a"));
	}
	
	public boolean isMatchDP(String str, String exp) {
		if (str == null || exp == null) {
			return false;
		}
		char[] s = str.toCharArray();
		char[] e = exp.toCharArray();
		if (!isValid(s, e)) {
			return false;
		}
		// initDPMap  做出一张表，而且填好倒数两列，和最后一行
		boolean[][] dp = initDP(s, e);
		for (int i = s.length - 1; i > -1; i--) {
			for (int j = e.length - 2; j > -1; j--) {
				if (e[j + 1] != '*') {
					dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
				} else {
					int si = i;
					while (si != s.length && (s[si] == e[j] || e[j] == '.')) {
						if (dp[si][j + 2]) {
							dp[i][j] = true;
							break;
						}
						si++;
					}
					if (dp[i][j] != true) {
						dp[i][j] = dp[si][j + 2];
					}
				}
			}
		}
		return dp[0][0];
	}
	
	public static boolean[][] initDP(char[] s, char[] p) {
		int slen = s.length;
		int elen = p.length;
		boolean[][] dp = new boolean[slen + 1][elen + 1];
		dp[slen][elen] = true;
		for (int j = elen - 2; j > -1; j = j - 2) {
			if (p[j] != '*' && p[j + 1] == '*') {
				dp[slen][j] = true;
			} else {
				break;
			}
		}
		if (slen > 0 && elen > 0) {
			if ((p[elen - 1] == '.' || s[slen - 1] == p[elen - 1])) {
				dp[slen - 1][elen - 1] = true;
			}
		}
		return dp;
	}
	
	private boolean isValid(char s[], char p[]) {
		for (int i = 0; i < s.length; i++) {
			if (s[i] == '.' || s[i] == '*') {
				return false;
			}
		}
		for (int i = 0; i < p.length; i++) {
			if (p[i] == '*' && (i == 0 || p[i - 1] == '*')) {
				return false;
			}
		}
		return true;
	}
}
